/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/19
 */
//约瑟夫问题10E100版
//    n个人排成一圈。从某个人开始，按顺时针方向依次编号
//    从编号为1的人开始顺时针“一二一”报数
//    报到2的人退出圈子
//    试问最后剩下的人最开始的编号。
public class P7_4_1095 {

    public static int test(int n) {
        List<Circle> circles = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            circles.add(new Circle(i + 1));
        }
        for (int i = 0; i < circles.size(); i++) {
            Circle circle = circles.get(i);
            if (i == 0) {
                circle.setNext(circles.get(i + 1)).setPrevious(circles.get(circles.size() - 1));
            } else if (i == circles.size() - 1) {
                circle.setNext(circles.get(0)).setPrevious(circles.get(i - 1));
            } else {
                circle.setPrevious(circles.get(i - 1)).setNext(circles.get(i + 1));
            }
        }
        Circle cur = circles.get(0);
        Circle next = cur.getNext().getNext();
        cur.setNext(next);
        while (cur.getNext() != cur) {
            cur = cur.getNext();
            next = cur.getNext().getNext();
            cur.setNext(next);
        }
        return (int) cur.getValue();
    }

    // 循环列表
    static class Circle {
        private Object oldValue;
        private Object value;
        private Circle next;
        private Circle previous;

        public Circle(Object value) {
            this.value = value;
            this.oldValue = value;
        }

        public void updateValue() {
            this.oldValue = this.value;
        }

        public Object getValue() {
            return value;
        }

        public static void print(List<P5_1_1554.Circle> circles) {
            int[] result = new int[circles.size()];
            for (int i = 0; i < circles.size(); i++) {
                result[i] = (int) circles.get(i).getValue();
            }
            System.out.println("circles:");
            printArray(result);
        }

        public Object getOldValue() {
            return oldValue;
        }

        public Circle setOldValue(Object oldValue) {
            this.oldValue = oldValue;
            return this;
        }

        public Circle setValue(Object value) {
            this.value = value;
            return this;
        }

        public Circle getNext() {
            return next;
        }

        public Circle setNext(Circle next) {
            this.next = next;
            return this;
        }

        public Circle getPrevious() {
            return previous;
        }

        public Circle setPrevious(Circle previous) {
            this.previous = previous;
            return this;
        }
    }

    // 打印int数组
    public static void printArray(int[] values) {
        StringBuilder sb = new StringBuilder().append('[');
        for (int i = 0; i < values.length; i++) {
            if (i != values.length - 1) {
                sb.append(values[i]).append(", ");
            } else {
                sb.append(values[i]);
            }
        }
        sb.append(']');
        System.out.println(sb.toString());
    }

    public static void main(String[] args) {
        System.out.println(test(9));
    }
}
